The present invention pertains generally to data integrity in data recording/recovery devices, and more particularly to a multi-level error detection and correction technique.
Data storage devices, which are used in both short- and long-term capacities, are an integral part of modern computer systems. While factors such as costs, device form factor, storage media size and capacity, and recording and recovery times are of high importance, of primary concern is the ability to maintain data integrity.
Techniques have been developed to detect and even correct data errors. In one technique, a cyclical redundancy code (CRC) is generated over the data and recorded along with the data to the storage media. During the recovery of the data from the storage media during a later session, the CRC is regenerated from the recovered data and compared to the recorded CRC accompanying the data to determine whether or not the data contains an error. CRCs are useful in detection of errors; however, they do not indicate the location of the error.
Error correction code (ECC) techniques have been developed in response to this problem. As the name implies, ECC techniques not only detect data errors, but they are also used to correct errors. One powerful error detection technique in common use is known as the Reed-Solomon error correction code.
As with the CRC code, an ECC is often generated over, and stored along with, the data to be recorded to the storage media. Upon recovery of the data, the recovered data and accompanying recorded ECC are sent through the ECC generator, which detects and corrects up to a certain number of errors in the recovered data.
Storage device manufacturers conventionally employ CRC and ECC techniques, at least to some degree, in the design of the data format and associated read/write logic to ensure data integrity. Typically, only a single or at most double level of error correction is performed. If bad data is detected and cannot be corrected using the single- or double-level ECC techniques, the data must be re-read from the storage medium to attempt once again to recover it. At the very least, this is a time-consuming process. Depending on the media type, this can also cause damage to the media itself, as in the case of magnetic tape devices where re-reads require a backhitching sequence that causes wear on the magnetic tape. Accordingly, a need exists for a more robust data recovery and error correction technique to maximize the number of data errors that can be corrected without having to re-read the data.
In addition, because recovered data is typically sent to the host system in pre-defined blocks of data of ordered addresses, the inability to recover a single or a few data bytes within a given block of data delays the delivery of the entire block of data to the host until the xe2x80x9cmissingxe2x80x9d data is corrected or recovered. Accordingly, in systems with only single- or double-layer error correction, more of the data must be recovered from the storage media itself as actual good data. As previously mentioned, if error correction cannot correct the recovered data using the single- or double-layer error correction techniques of the device, the data must be re-read from the storage media, causing significant delay to the host in recovering the data. Accordingly, a need also exists for a technique for increasing the error correction rate in order to reduce the number of re-reads from the storage medium.
The present invention is a novel method and apparatus for providing multi-level error correction for data stored on a storage medium. In accordance with the invention, error correction is performed on data packets recovered from the storage medium at both the packet level and at the segment level. Segment level error correction is performed over multiple instances of multiple patterns of buffer packets located in the buffer to correct (i.e., generate) missing packets not yet read from the storage medium.
The invention reduces the number of re-reads of data from the storage medium by providing very powerful multi-level error correction of the data read during the first pass. The ability to generate missing packets from recovered good packets already present in the data buffer reduces the need to backhitch and actually reread data that was not properly detected during the first pass of the read head(s) over the track packet. A reduced number of backhitching sequences results in improved data recovery time as seen by the host.